package base;

/**
 * @author mazouri
 * @create 2021-12-27 11:24
 */
public class _4_lcs {
    char[] c1;
    char[] c2;

    public int lcs(String s1, String s2) {
        this.c1 = s1.toCharArray();
        this.c2 = s2.toCharArray();
        return helper(c1.length-1, c2.length-1);
    }

    private int helper(int i, int j) {
        if (i < 0 || j < 0) return 0;
        //abcde ace 第一个字符相等 ， 这个字符一定在lcs中 加1 然后比较后面的
        if (c1[i] == c2[j]) return 1 + helper(i -1, j - 1);
        /**
         * 不相等，s1[i]和s2[j]中至少有一个字符不在lcs中 则肯定包含三种情况
         1. s1串中的第一个字符不在公共子序列 bcde ce
         2. s2串中的第一个字符不在公共子序列
         3. 两个首字符都不在公共子序列中，但此时的公共子序列长度一定小于等于上面两种情况
         */
        else return Math.max(helper(i - 1, j), helper(i, j - 1));
    }

    public static void main(String[] args) {
        _4_lcs o = new _4_lcs();
        System.out.println(o.lcs("abcde", "ace"));
    }
}
